Hoàng Mai vốn trước là vùng đất thuộc huyện Thanh Trì. Vùng Hoàng Mai có tên Nôm là Kẻ Mơ và tên chữ là Cổ Mai, vì mai là tiếng Hán của mơ, do trước kia nơi đây người dân sinh sống chủ yếu bằng trồng cây mai. Lại có rất nhiều các giống mai được trồng nên ta có thể giải thích lại có một loạt các địa danh như: Tương Mai, Thanh Mai, Hồng Mai, Bạch Mai, Hoàng Mai...

Năm 1390, danh tướng Trần Khát Chân sau khi có công giết chết vua Chiêm là Chế Bồng Nga và đánh tan quân Chiêm Thành đã được ban thái ấp ở vùng đất Cổ Mai.

Thời nhà Lê, vùng đất này thuộc huyện Thanh Trì, phủ Thường Tín, trấn Sơn Nam Thượng.

Đến thời Nguyễn, tỉnh Hà Nội được thành lập. Vùng đất Hoàng Mai lúc này thuộc huyện Thanh Trì, phủ Thường Tín, tỉnh Hà Nội.

Sau khi thành Hà Nội bị cắt nhượng cho Pháp, huyện Thanh Trì thuộc phủ Thường Tín, tỉnh Hà Đông.

Tháng 9 năm 1947, huyện Thanh Trì được sáp nhập vào Hà Nội.

Ngày 9 tháng 8 năm 1973, 2 thôn Giáp Bát, Giáp Lục của xã Thịnh Liệt, thôn Tương Mai và một phần đất thôn Mai Động thuộc xã Hoàng Văn Thụ, huyện Thanh Trì được cắt về khu phố Hai Bà Trưng.

Ngày 13 tháng 10 năm 1982, thành lập phường Mai Động thuộc quận Hai Bà Trưng và tách xóm Mã Cả của xã Hoàng Văn Thụ thuộc huyện Thanh Trì về phường Tương Mai, quận Hai Bà Trưng.

Ngày 14 tháng 3 năm 1984, chia phường Giáp Bát thuộc quận Hai Bà Trưng thành 2 phường Giáp Bát và Tân Mai.

Ngày 26 tháng 10 năm 1990, chuyển toàn bộ diện tích tự nhiên và nhân khẩu của xã Hoàng Văn Thụ thuộc huyện Thanh Trì về quận Hai Bà Trưng quản lý và chuyển thành phường Hoàng Văn Thụ.

Quận Hoàng Mai được thành lập vào ngày 6 tháng 11 năm 2003 theo Nghị định số 132/2003/NĐ-CP[1] trên cơ sở tách 9 xã: Định Công, Đại Kim, Hoàng Liệt, Thịnh Liệt, Thanh Trì, Lĩnh Nam, Trần Phú, Vĩnh Tuy, Yên Sở, 55 ha diện tích tự nhiên của xã Tứ Hiệp thuộc huyện Thanh Trì và 5 phường: Mai Động, Tương Mai, Tân Mai, Giáp Bát, Hoàng Văn Thụ thuộc quận Hai Bà Trưng, đồng thời chuyển 8 xã: Định Công, Đại Kim, Hoàng Liệt, Thịnh Liệt, Thanh Trì, Lĩnh Nam, Trần Phú, Yên Sở thành 8 phường có tên tương ứng; chuyển xã Vĩnh Tuy thành phường Vĩnh Hưng (để tránh nhầm lẫn với phường Vĩnh Tuy của quận Hai Bà Trưng).